package binarytree

// 思路：
// ----------层序遍历
// 维持三个队列
// 队列1和2维持两棵树的所有节点，注意按照层的顺序，而且要包含层中的nil元素。
// 队列3维持新树的节点：队列3中的节点的生成规则是：
// 如果此时队列3是空的，那么从队列1和队列2中对位拿出元素相加得到一个新的根节点。
// 否则的话：
// 从队列1和队列2中对位拿出元素相加得到一个新的左节点，再执行一遍相同的操作得到新的右节点
// 然后从队列3中拿出一个节点，将上边的两个节点挂上即可
// 直到队列1和2都没有节点就结束。
// ----------
// 递归也不难理解
// 同时访问 root1 和 root2 的相同层级的节点，然后相加得到新节点，递归访问 root1.Left&root2.Left 得到新节点
func MergeTreesIterate(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	node := &TreeNode{}
	if root1 == nil {
		node = root2
		return node
	} else if root2 == nil {
		node = root1
		return node
	} else {
		node = &TreeNode{Val: root1.Val + root2.Val}
	}

	node.Left = MergeTreesIterate(root1.Left, root2.Left)
	node.Right = MergeTreesIterate(root1.Right, root2.Right)
	return node
}
